#include<bits/stdc++.h>
#define gc getchar
#define itn int
#define x first
#define y second
#define eb emplace_back
#define em emplace
#define pb push_back
#define db double
#define y1 yy1_yyds
using namespace std; typedef long long ll; typedef unsigned long long ull;
// https://www.luogu.com.cn/discuss/522581 About "const"
ll read() {
	ll x = 0; short fh = 1; char ch = gc();
	while (!isdigit(ch)) {
		if (ch == '-') fh = -1;
		if (ch < 10) exit(0); 
		ch = gc();
	}
	while (isdigit(ch))
		x = x * 10 + (ch ^ 48), ch = gc();
	return fh * x;
}
#ifndef ONLINE_JUDGE
void debug() {cerr << "\n";}
template<typename Typ1> void debug(Typ1 arg) {cerr << arg << "\n";}
template<typename Typ1, typename ...Typ2> void debug(Typ1 arg, Typ2 ...args) {
	cerr << arg << " ", debug(args...);
}
#else
void debug() {}
template<typename Typ1> void debug(Typ1 arg) {}
template<typename Typ1, typename ...Typ2> void debug(Typ1 arg, Typ2 ...args) {}
#endif
void writeln(ll arg) {printf("%lld\n", arg);}
template<typename ...Typ2> void writeln(ll arg, Typ2 ...args) {
	printf("%lld ", arg), writeln(args...);
}
typedef pair <int, int> pii; typedef pair <ll, ll> pll;
const char Y_E_S[] = "YES", N__O[] = "NO";
// const char Y_E_S[] = "Yes", N__O[] = "No";
// #define infinite_testcase
// #define multiple_testcase
// #define output_Yes_No
const int DUST = 327, N = 114514, M = -1;
int n, q;
namespace Sub1 {
	void major() {
		string a = "0", b = "1";
		for(int i = 3; i <= n; i++) {
			string c = b + a;
			a = b, b = c;
		}
		while(q--) {
			cin >> a;
			int t = 0;
			#define n (int)b.length()
			for(int i = /*1*/0; i <= n - (int)a.length(); i++)
				for(int l = i, j = 0; l < n && j < (int)a.length(); l++, j++) {
					if(b[l] != a[j]) break;
					if(j == (int)a.length() - 1) t++;
				}
			#undef n
			writeln(t);
		}
	}
}
const int mod = 1e9 + 7;

namespace Sub3 {
	int _0[N], _1[N], _11[N];
	char s[N];
	int query() {
		if(strlen(s) > 2) return 0;
		if(s[1] == '0') return 0;
		if(s[1]) return _11[n];
		if(s[0] == '1') return _1[n];
		else return _0[n];
	}
	void major() {
		_0[1] = _1[2] = _0[3] = _1[3] = 1;
		for(int i = 4; i <= n; i++) {
			_0[i] = (_0[i - 1] + _0[i - 2]) % mod,
			_1[i] = (_1[i - 1] + _1[i - 2]) % mod,
			_11[i] = (_11[i - 1] + _11[i - 2] + (/*n 我tm……*/i & 1)/*合并的时候会多一个11*/) % mod;
			// debug(_11[i]);
		}
		while(q--) {
			scanf("%s", s);
			writeln(query());
		}
	}
}
bool major(int Case = 1) {
	n = read(), q = read();
	if(n <= 10) return Sub1::major(), 1;
	return Sub3::major(), 1;
	return Case ^= Case ^ Case;
}
void initial_function(int argc, char **argv) {
	**argv = argc; /* <- place_holder
	you won't give up no matter what happens, will you?
	code time: >> 11:53
	---
	
	*/
	freopen("brotherhood.in", "r", stdin);
	freopen("brotherhood.out", "w", stdout);
}
signed main(int argc, char **argv) {
	initial_function(argc, argv);
	int Case = 1, Maxcase = 1;
	for (
#ifdef multiple_testcase
		  Maxcase = read()
#endif
				     	  ;
#ifndef infinite_testcase
							Case <= Maxcase
#endif
				     					   ; Case++)
#ifdef output_Yes_No
		puts(major(Case) ? Y_E_S : N__O);
#else
		major(Case);
#endif
	return DUST ^ 0x147;
}
